package org.niu.backtracking;

import java.util.ArrayList;

public class Permute {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        boolean[] visited = new boolean[num.length];
        ArrayList<Integer> l = new ArrayList<>();
        backtracking(num,visited,l);
        return ans;
    }
    void backtracking(int[] num, boolean[] visited,ArrayList<Integer> list){
        if(list.size() == num.length){
            if(!ans.contains(list)){
                ans.add(new ArrayList<>(list));
            }
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if(!visited[i]){
                visited[i]=true;
                list.add(num[i]);
                backtracking(num,visited,list);
                list.remove(list.size()-1);
                visited[i] =false;
            }
        }
    }
}
